package com.github.tangmonkmeat;

/**
 * Description:
 *
 * @author zwl
 * @version 1.0
 * @date 2021/5/21 下午3:01
 */
public class 不相交的线 {

    public static void main(String[] args) {
        int[] num1 = {1,3,7,1,7,5};
        int[] num2 = {1,9,2,5,1};
        System.out.println(maxUncrossedLines2(num1, num2));
    }

    public static int maxUncrossedLines2(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
                }
            }
        }
        return dp[m][n];
    }

    static int max = 0;

    public static int maxUncrossedLines(int[] nums1, int[] nums2) {
        def(nums1, nums2, 0, 0, 0);
        return max;
    }

    public static void def(int[] num1, int[] num2, int a, int b, int curr) {
        if (a >= num1.length) {
            max = Math.max(max, curr);
            return;
        }
        for (int j = a; j < num1.length; j++) {
            for (int i = b; i < num2.length; i++) {
                if (num1[j] == num2[i]) {
                    def(num1, num2, j + 1, i + 1, curr + 1);
                    def(num1, num2, j + 2, b, curr);
                }
            }
            max = Math.max(max, curr);
        }
    }
}
